/* 查找最小的 k 个元素 (数组)
 * 题目：输入 n 个整数，输出其中最小的 k 个
 * 例如输入 1, 2, 3, 4, 5, 6, 7 和 8 这 8 个数字，
 * 则最小的 4 个数字为 1, 2, 3 和 4
 */
#include <stdio.h>

int getmax(int const b[], int const k) {
  int i, max;
  for (i=1, max=0; i < k; i++)
    if (b[max] < b[i]) max = i;

  return max;
}

void getkmin(int const a[], int const n, int b[], int const k) {
  int i, max;
  for (i = 0; i < n; i++)
    if (i < k) b[i] = a[i];
    else {
      max = getmax(b, k);
      if (b[max] > a[i]) b[max] = a[i];
    }

  return;
}

#define A_SIZE 8
#define B_SIZE 4

int main() {
  int a[A_SIZE] = {28,9,18,109,8,189,7,99};
  int b[B_SIZE];
  int i;

  getkmin(a, A_SIZE, b, B_SIZE);
  printf("a[%u]:", A_SIZE);
  for (i = 0; i < A_SIZE; i++)
    printf(" %d", a[i]);

  printf("\nb[%u]:", B_SIZE);
  for (i = 0; i < B_SIZE; i++)
    printf(" %d", b[i]);

  printf("\n");

  return 0;
}
